/**
 * 找一个二叉树的公共祖先，这里指针形式的树，不可用随机访问
 * 所以实现起来比数组树要麻烦一点
 * 
 * 后续遍历最后访问根节点
 * 
 * 现在有节点p和q
 * 采用后续非递归算法，栈中存放二叉树节点的指针，当访问到某个节点时，栈中所有元素都是改节点的祖先。
 * 而对于后续遍历，必定先访问到左边的那个节点。
 * 当访问到左边节点的时候，将这个栈拷贝到另一个辅助栈中。
 * 继续查找，直到右边的那个节点，此时结束查找
 * 开始将这两个栈进行匹配，第一个匹配相等的元素就是节点p和q的公共祖先
 */

#include"BiTree.h"
typedef struct 
{
    BiTree* t;
    int tag;//0表示左子树被访问过，1表示右
}S;
S s[],s1[];//两个辅助栈

int top=0;
BiTree *bt;
int i=0;
int j=0;
/**
 * 找两个节点公共祖先
 * @param root 树
 * @param p 节点1
 * @param q 节点2
 * 
 */
BiTree* ancestor(BiTree *root,BiTree *p,BiTree *q){
    //top是栈顶指针（初始值为0）bt作为根的临时节点，进行遍历
    top=0;bt=root;
    while (bt!=nullptr||top>0)
    {
        while (bt!=nullptr)//沿着左分支往下
        {
            s[++top].t=bt;//可能是书的问题，top初值为0，应该先赋值后加加
            s[top].tag=0;//标记左节点被访问，然后移动到左子树
            bt=bt->left;
        }
        while (top!=0&&s[top].tag==1)//如果p在q的左侧，遇到p的时候，栈中元素全是p的祖先
        {
            if(s[top].t==p){
                for(i=1;i<top;i++){
                    s1[i]=s[i];
                    top1=top;
                }
            }//将栈s的元素转入s1保存
            if(s[top].t==q){//找到q节点
                for(i=top;i>0;i--){
                    if(s1[j].t==s[i].t){
                        return s[i].t;//p和q的公共祖先已经找到
                    }
                }
                top--;//退栈
            }
        }
        if(top!=0){
            s[top].tag=1;
            bt=s[top].t->right;//沿着右分支往下遍历
        }
        
    }
    return nullptr;//没有公共祖先
    
}

